/*
 * @Author: 缄默
 * @Date: 2021-12-08 20:25:17
 * @LastEditors: 缄默
 * @LastEditTime: 2021-12-09 19:54:00
 */

//信封嵌套问题

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
class Envelope {
public:
    int len;
    int wight;
    Envelope(int weight, int hight) : len(weight), wight(hight) {};

    //重载类的＜号比较运算符，使其放入容器后可以使用algorithm中的函数
    bool operator < (Envelope& env) {
        if (this->len < env.len) return true;
        else if (this->len == env.len) {
            if (this->wight > env.wight) return true;
        }
        return false;
    }
};

//打印函数 判断其中是否正确
void print(vector<Envelope>& arr);

//获得最大信封数
int getMax(vector<Envelope>& arr);
int main() {
    vector<Envelope> arr;
    vector<vector<int>> num{{3 ,4}, {2, 3}, {4, 5}, {1, 3}, {2, 2}, {3, 6}, {1, 2}, {3, 2}, { 2, 4}};
    for (auto x : num) {
        arr.emplace_back(Envelope(x[0], x[1]));
    }
    //对arr进行排序
    sort(arr.begin(), arr.end());
    //调用函数求最大数量
    cout << getMax(arr) << endl;
    return 0;
}

void print(vector<Envelope>& arr) {
    for (auto x : arr) {
        cout << "{" << x.len << ", " << x.wight << "}, ";
    }
    cout << endl;
}

//该方法参照P210.cpp最优解法理解 最长递增子序列最优求法
int getMax(vector<Envelope>& arr) {
    vector<int> ends(arr.size());
    int right = 0;
    ends[0] = arr[0].wight;
    for (int i = 0; i < arr.size(); i++) {
        int l = 0;
        int r = right;
        while (l <= r) {
            int m = (l + r) / 2;
            if (arr[i].wight > ends[m]) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        right = right < l ? l : right;
        ends[l] = arr[i].wight;
        // if (l < right) {
        //     ends[l] = arr[i].wight;
        // }
        // else {
        //     ends[right] = arr[i].wight;
        //     right++;

        // }
    }
    return right + 1;
}